/*
自顶向下的归并排序
*/

#include <iostream>
using namespace std;

void Merge(int* arr1,int len1,int* arr2,int len2){
	int* tmp = new int[len1+len2];
	int i = 0,j = 0,k = 0;
	while( i != len1 && j != len2){
		if(arr1[i] <= arr2[j]){
			tmp[k++] = arr1[i++];
		}
		else{
			tmp[k++] = arr2[j++];
		}
	}
	while(j < len2){
		tmp[k++] = arr2[j++];
	}
	while(i < len1){
		tmp[k++] = arr1[i++];
	}
	for(i = 0;i < k;i++){
		arr1[i] = tmp[i];
	}
	delete []tmp;
	tmp = NULL;
}
void MergeSort(int* arr,int len){
	if(len > 1){
		int* arr1 = arr;
		int arr1_len = len/2;
		int* arr2 = arr + arr1_len;
		int arr2_len = len - arr1_len;
		//分解
		MergeSort(arr1,arr1_len);
		MergeSort(arr2,arr2_len);
		//合并
		Merge(arr1,arr1_len,arr2,arr2_len);
	} 
}

void Print(int* arr,int len){
	for(int i = 0;i < len;i++){
		cout<<arr[i]<<"  ";
	}
	cout<<endl;
}
int main(int argc, char const *argv[])
{
	int arr[8] = {2,4,11,0,1,9,6,7};
	Print(arr,8);
	MergeSort(arr,8);
	Print(arr,8);
	
	return 0;
}